﻿#pragma once

//主模板 HashFunc<K> 提供默认行为，适用于可以直接转换为 size_t 的类型（如 int、long、char 等）。
template <class K>
struct HashFunc {
	size_t operator()(const K& key) { return (size_t)key; }
};

//特化版本 HashFunc<string> 针对 string 类型，提供更合理的哈希计算方式（BKDR Hash）。
template <>
struct HashFunc<string> {
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (auto e : key) {
			hash *= 31;//为了解决"abc" "acb"结果相同(BKDR)
			hash += e;
		}
		return hash;//返回string中所有字符ASCII码值相加		
	}
};
//标准库中的unordered_map并不需要手动传第三个参数就可以处理string
//因为使用的是模版特化
//struct HashFuncString {
//	size_t operator()(const string& key) { 
//		size_t hash = 0;
//		for (auto e : key) {
//			hash *= 31;//为了解决"abc" "acb"结果相同(BKDR)
//			hash += e;
//		}			
//		return hash;//返回string中所有字符ASCII码值相加		
//	}
//};

//闭散列 / 开放定址法
namespace open_address {
	enum Status {
		EMPTY,
		EXIST,
		DELETE
	};

	template <class K, class V>
	struct HashData {
		pair<K, V> _kv;
		Status _s;
	};

	//如果key是string无法直接取模映射，所以需要仿函数
	//由于有些key(例如int)可以直接取模，所以仿函数设置为缺省参数
	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable {
	public:
		HashTable() {
			_tables.resize(10);
		}
		bool Insert(const pair<K, V>& kv) {
			//不允许重复值。所以插入前先查找，如果找到就退出。
			if (Find(kv.first)) return false;

			//负载因子太大，冲突剧增，效率降低
			//负载因子太小，冲突降低，空间利用率低
			//if (_n / _tables.size() == 0.7) { //_n和_tables.size()都是无符号整数，相除不会得到浮点数
			if (_n * 10 / _tables.size() == 7) { //两边同时乘10
				//size_t newSize = _tables.size() * 2;
				//_tables.resize(newSize);
				//数据的位置要模_tables.size()，直接扩2倍导致数据的映射关系发生变化

				//扩容需要三步：
				//开新空间、重新映射、释放旧空间
				size_t newSize = _tables.size() * 2;
				HashTable<K, V, Hash> newHT;//创建新表
				newHT._tables.resize(newSize);//新表开空间是原表2倍
				for (size_t i = 0; i < _tables.size(); i++)//将原表的数据插入到新表
					if (_tables[i]._s == EXIST)
						newHT.Insert(_tables[i]._kv);
				_tables.swap(newHT._tables);
				//这里不用手动释放。因为newHT是这个if条件里的局部对象，出了作用域调用析构函数。
				//且HashTable没有写析构函数，自动生成的析构函数对自定义类型调用它的析构函数(即vector的析构函数)
			}
			//线性探测
			Hash hf;
			//只能模size是因为vector的operator[]只能访问[0, size())范围内的元素
			size_t hashi = hf(kv.first) % _tables.size();//如果key是string无法直接取模，所以需要仿函数
			while (_tables[hashi]._s == EXIST) { //如果hashi位置状态为存在
				++hashi;//向后移动
				hashi %= _tables.size();//为防止越界，需要取模。
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;
			return true;
		}

		HashData<K, V>* Find(const K& key) {
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			//因为线性探测的冲突解决规则，导致相同哈希值的数据会聚集在一起，
			//所以 Find 在遇到 DELETE 状态时必须继续向后查找
			//而下方Erase是伪删除法，只是将状态置为DELETE，但数据还在，所以删除后，Find去查找，依然能找到
			while (_tables[hashi]._s != EMPTY) { //只要不是EMPTY就继续找（包括DELETE和EXIST）
				//if (_tables[hashi]._kv.first == key) //这样会导致删除的元素仍能被找到
				if (_tables[hashi]._s == EXIST
					&& _tables[hashi]._kv.first == key)//只有EXIST且key匹配才算找到
					return &_tables[hashi];
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key) {
			HashData<K, V>* ret = Find(key);
			if (ret) {
				ret->_s = DELETE;
				--_n;
				return true;
			}
			else
				return false;
		}

		void Print() {
			for (size_t i = 0; i < _tables.size(); i++) {
				if (_tables[i]._s == EXIST)
					//printf("[%d]->%d\n", i, _tables[i]._kv.first);//只能打印key是int类型
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				else if (_tables[i]._s == EMPTY)
					printf("[%d]->\n", i);
				else
					printf("[%d]->D\n", i);
			}
			cout << endl;
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//存储的关键字的个数
		//1.如何判断某个位置是否储存了值
		//2.由于Find遇到空才停止，如果删除了某个值，怎么Find它后面的值
		//不能全找，这样就不符合哈希表查找的效率
		//所以每个位置需要标记状态
	};

	void TestHT1() {
		HashTable<int, int> ht;
		int a[] = { 4,14,24,34,5,7,1 };
		for (auto e : a)
			ht.Insert(make_pair(e, e));
		ht.Insert(make_pair(3, 3));
		ht.Insert(make_pair(3, 3));
		ht.Insert(make_pair(-3, -3));
		//插入负数没影响，因为映射时取模size是无符号数
		//负数整形会提升为无符号数
		ht.Print();

		ht.Erase(3);
		ht.Print();

		ht.Insert(make_pair(3, 3));
		ht.Insert(make_pair(23, 3));
		ht.Print();
	}

	void TestHT2() {
		string arr[] = { "香蕉", "甜瓜", "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		HashTable<string, int> ht;
		for (auto& e : arr) {
			HashData<string, int>* ret = ht.Find(e);
			if (ret) ret->_kv.second++;
			else ht.Insert(make_pair(e, 1));
		}
		ht.Print();
	}
}



//开散列 / 链地址法(开链法)
namespace hash_bucket {
	//template <class K, class V>
	//struct HashNode {

	//};
	//template <class K, class V>
	//class HashTable {
	//	typedef HashNode<K, V> Node;
	//private:
	//	//如果只为了实现哈希表，用这个
	//	//struct bucket {
	//	//	forward_list<pair<K, V>> _lt;
	//	//	set<pair<K, V>> _rbtree;
	//	//	size_t len = 0;//超过8改为红黑树
	//	//};
	//	//vector<bucket> _tables;//不选择这种方式是因为需要自己实现迭代器

	//	vector<Node*> _tables;
	//	size_t _n = 0;
	//};

	template <class K, class V>
	struct HashNode {
		HashNode* _next;
		pair<K, V> _kv;

		HashNode(const pair<K, V>& kv)
			:_next(nullptr)
			, _kv(kv) {
		}
	};
	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<K, V> Node;
	public:
		//vector<Node*> 调用 resize(10) 后，所有指针会被默认初始化为 nullptr
		//（因为 Node* 是内置指针类型，默认初始化是未定义的，但 resize 会进行值初始化，即 nullptr）。
		HashTable() { _tables.resize(10, nullptr); }

		//因为哈希桶的vector每个位置的数据是一串链表
		//自动生成的析构只会释放vector，所以需要自己实现析构去释放链表
		~HashTable() {
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				while (cur) {
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv) {
			if (Find(kv.first)) return false;//不允许重复key
			Hash hf;
			//哈希桶不扩容不会死循环，但每个桶装太多数据效率低
			//哈希桶负载因子最大是1
			//if (_n == _tables.size()) {
			//	//如果使用闭散列的逻辑会有问题，开散列的哈希表每个位置是一个哈希桶(即链表)
			//	//重新创建新链表，释放就链表消耗很大
			//	size_t newSize = _tables.size() * 2;
			//	HashTable<K, V> newHT;
			//	newHT._tables.resize(newSize);
			//	for (size_t i = 0; i < _tables.size(); i++) {
			//		Node* cur = _tables[i];
			//		while (cur) {
			//			newHT.Insert(cur->_kv);
			//			cur = cur->_next;
			//		}
			//	}
			//	_tables.swap(newHT._tables);
			//}
			if (_n == _tables.size()) {
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->_next;
						size_t hashi = hf(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;//旧表中i的位置依然指向新表，如果不置空，析构会有问题
				}
				_tables.swap(newTables);
				//让 _tables 指向扩容后的新表。
				//让 newTables 接管旧表，通过析构自动释放内存。
			}
			size_t hashi = hf(kv.first) % _tables.size();//key映射到哈希表的位置
			Node* newnode = new Node(kv);
			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

		Node* Find(const K& key) {
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur) {
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key) {
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur) { //遍历哈希桶
				if (cur->_kv.first == key) { //如果找到了
					if (prev == nullptr) //且是第一个
						_tables[hashi] = cur->_next;
					else
						prev->_next = cur->_next;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		void Some() {
			size_t bucketSize = 0;//有多少个桶
			size_t maxBucketLen = 0;//单个桶最大长度
			size_t sum = 0;//元素总数
			double averageBucketLen = 0;//平均桶长度
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				if (cur) ++bucketSize;
				size_t bucketLen = 0;//单个桶长度
				while (cur) {
					++bucketLen;
					cur = cur->_next;
				}
				sum += bucketLen;
				if (bucketLen > maxBucketLen) maxBucketLen = bucketLen;
			}
			averageBucketLen = (double)sum / (double)bucketSize;
			cout << "all bucketSize:" << _tables.size() << endl;
			cout << "bucketSize:" << bucketSize << endl;
			cout << "maxBucketLen:" << maxBucketLen << endl;
			cout << "averageBucketLen:" << averageBucketLen << endl;
			cout << endl;
		}
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};

	void TestHT1() {
		HashTable<int, int> ht;
		int a[] = { 4,14,24,34,5,7,1,15,25,3 };
		for (auto e : a)
			ht.Insert(make_pair(e, e));
		ht.Insert(make_pair(13, 13));
		cout << ht.Find(4) << endl;
		ht.Erase(4);
		cout << ht.Find(4) << endl;
	}

	void TestHT2() {
		string arr[] = { "香蕉", "甜瓜", "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		HashTable<string, int> ht;
		for (auto& e : arr) {
			HashNode<string, int>* ret = ht.Find(e);
			if (ret) ret->_kv.second++;
			else ht.Insert(make_pair(e, 1));
		}
	}

	void TestHT3() {
		const size_t N = 1000000;

		unordered_set<int> us;
		set<int> s;
		HashTable<int, int> ht;

		vector<int> v;
		v.reserve(N);
		srand((size_t)time(0));
		for (size_t i = 0; i < N; ++i) {
			//v.push_back(rand()); // N比较大时，重复值比较多
			v.push_back(rand() + i); // 重复值相对少
			//v.push_back(i); // 没有重复，有序
		}

		size_t begin1 = clock();
		for (auto e : v)
			s.insert(e);
		size_t end1 = clock();
		cout << "set insert:" << end1 - begin1 << endl;

		size_t begin2 = clock();
		for (auto e : v)
			us.insert(e);
		size_t end2 = clock();
		cout << "unordered_set insert:" << end2 - begin2 << endl;

		size_t begin10 = clock();
		for (auto e : v)
			ht.Insert(make_pair(e, e));
		size_t end10 = clock();
		cout << "HashTable insert:" << end10 - begin10 << endl << endl;


		size_t begin3 = clock();
		for (auto e : v)
			s.find(e);
		size_t end3 = clock();
		cout << "set find:" << end3 - begin3 << endl;

		size_t begin4 = clock();
		for (auto e : v)
			us.find(e);
		size_t end4 = clock();
		cout << "unordered_set find:" << end4 - begin4 << endl;

		size_t begin11 = clock();
		for (auto e : v)
			ht.Find(e);
		size_t end11 = clock();
		cout << "HashTable find:" << end11 - begin11 << endl << endl;

		cout << "插入数据个数：" << s.size() << endl;
		ht.Some();

		size_t begin5 = clock();
		for (auto e : v)
			s.erase(e);
		size_t end5 = clock();
		cout << "set erase:" << end5 - begin5 << endl;

		size_t begin6 = clock();
		for (auto e : v)
			us.erase(e);
		size_t end6 = clock();
		cout << "unordered_set erase:" << end6 - begin6 << endl;

		size_t begin12 = clock();
		for (auto e : v)
			ht.Erase(e);
		size_t end12 = clock();
		cout << "HashTable erase:" << end12 - begin12 << endl;
	}
}